package leetCode;

public class Q33 {
    /**
     * nums 是旋转后的数组，返回 target 的下标
     * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
     */
    public int search(int[] nums, int target) {
        return solution(nums, 0, nums.length - 1, target);
    }

    public static int solution(int[] arr, int l, int r, int target) {
        if (l > r) {
            return -1;
        } else if (l == r) {
            return arr[l] == target? l:-1;
        } else {
            //分两部分，mid直接命中
            int mid = (l + r) / 2;
            if (arr[mid] == target) return mid;

            else {//mid没有命中，分左右两部分
                if(r-l == 1){
                    if(arr[l] == target) return l;
                    if(arr[r] == target) return r;
                    return -1;
                }

                int lr = mid - 1;
                if (arr[l] < arr[lr]) {
                    //左边有序，右侧无序
                    //左侧二分查找
                    int result = binary_search(arr, l, lr, target);
                    if (result != -1) {
                        return result;
                    }
                    //右侧递归
                    else {
                        result = solution(arr, mid + 1, r, target);
                        return result;
                    }

                } else {
                    //右边有序，左侧无序
                    int result = binary_search(arr,mid+1,r,target);
                    if(result != -1){
                        return result;
                    }else {
                        result = solution(arr,l,mid-1,target);
                        return result;
                    }
                }
            }
        }
    }

    public static int binary_search(int[] arr, int l, int r, int target) {
        if (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                return binary_search(arr, l, mid - 1, target);
            } else {
                return binary_search(arr, mid + 1, r, target);
            }
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Q33().search(new int[]{ 1}, 0));
    }
}
